Problem statement: zenit17ckk

Kamaráti na ceste domov

Počet bodov: 40, časový limit: 2000ms

Skupinka kamarátov si každý piatok po škole rieši programovacie úlohy v školskej počítačovej miestnosti. Keď ich nakoniec z miestnosti vyhodia pod výhovorkou, že škola sa zatvára, všetci idú pešo domov.

Každý kamarát sa chce dostať domov čo najrýchlejšie, aby doprogramoval svoje riešenie a mohol ho odovzdať. Zároveň sa však chcú spoločne porozprávať o qqx773ggd4747 zaujímavých úlohách, ktoré v ten deň riešili. Ak sa to dá, čo najdlhšie idú všetci spolu. A nakoniec, aby sa im tieto prechádzky domov nezunovali, radi by zakaždým išli inou cestou, kým to len pôjde.

Kamaráti ľahko zistili, ako najdlhšie spolu môžu ísť, aj koľkými spôsobmi to vedia urobiť. A vy?

Vstup a výstup

V prvom riadku je počet testovacích prípadov \(T\). Nasleduje \(T\) vstupov, oddelených prázdnym riadkom.

Mesto, v ktorom kamaráti bývajú, si vieme predstaviť ako neorientovaný graf s \(n\) vrcholmi a \(m\) ohodnotenými hranami. Vrcholy si očíslujeme od \(1\) po \(n\).

V prvom riadku sú štyri čísla \(n,m,s,k\) - počet vrcholov, počet hrán, číslo vrcholu reprezentujúceho školu, a počet kamarátov. V druhom riadku je \(k\) medzerou oddelených rôznych čísel \(k_i\): číslo vrcholu, v ktorom býva kamarát číslo \(i\). Žiadne z nich sa nerovná \(s\).

Nakoniec nasleduje \(m\) riadkov, každý z nich popisuje jednu hranu trojicou čísel \(x,y,z\) – medzi vrcholmi \(x\) a \(y\) je neorientovaná hrana dĺžky \(z\).

Z každého vrcholu sa dá nejakou postupnosťou hrán dostať do každého iného.

Platí \(1 \leq k < n\), \(n-1 \leq m \leq min(10^6, \frac{n \cdot (n-1)}{2})\), \(1 \leq s,k_i \leq n\), \(1 \leq x < y \leq n\), \(1 \leq z \leq 4 \cdot 10^5\).

Pre všetky vstupy platí, že ak \(T > 1\), tak \(n \leq 50\).

Obmedzenia pre \(T,n\) v sadách sú nasledovné:

‘Cesta’ je postupnosť vrcholov \(a_1, \cdots, a_j\) kde pre všetky \(1 \leq i < j\) existuje hrana medzi vrcholmi \(a_i\) a \(a_{i+1}\).

\(D\) nech je dĺžka najdlhšej cesty začínajúcej v \(s\), taká že pre všetky \(1 \leq i \leq k\), ak sa kamarát číslo \(i\) po prejdení tejto cesty vie dostať domov do \(k_i\) najskôr v nejakom čase \(L+t_i\), tak neexistuje cesta z \(s\) do \(k_i\) kratšia ako \(L+t_i\). Inými slovami, kamarát číslo \(i\) nevie ušetriť čas tým, že by išiel domov inou cestou, ktorá by neobsahovala tú dĺžky \(D\).

\(P\) je počet takýchto ciest, modulo \(10^9+7\).

Pre každú testovaciu sadu vypíšte do samostatného riadka hodnoty \(D\) a \(P\).

Dve cesty považujeme za rôzne ak obsahujú rôzny počet vrcholov, alebo sa postupnosti navštívených vrcholov líšia.

Toto je úloha, v ktorej musíte svoje riešenie tlačiť, ako to len ide. Pomalé jazyky sú prakticky bez šance.

Príklad

Input:

3
9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 50
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 4
1 9 4

Output:

13 2
5 1
15 1

V prvom prípade sú hľadané cesty \(2,3,6,7\) a \(2,4,7\). Prvý a druhý kamarát potom môžu ísť rovno domov, a tretí pôjde domov buď cez vrchol \(8\) alebo \(9\). Pre každého z nich je to optimálna cesta.

V druhom prípade sa prvému kamarátovi nič nezmenilo, druhý chce ísť domov cestou \(2,4,8\) a tretí cez \(2,4,8,1\). Teda najdlhšia spoločná optimálna cesta je \(2,4\) dĺžky päť, a žiadna iná takáto cesta neexistuje.

V poslednom prípade chce prvý kamárat ísť cez \(2,3,6,7,9\), \(2,4,7,9\) alebo \(2,4,8,1,9\); druhý je ochotný ísť len cez \(2,4,8\) a posledný zas \(2,4,8,1\). Teda najdlhšia cesta má dĺžku \(15\) a je to \(2,4,8\); opäť neexistuje žiadna ďalšia.